package com.datastructure.test.topkstring;

import java.util.*;
import java.util.stream.Collectors;

public class TopKString {

    public static void main(String[] args) {
        TopKString topKString = new TopKString();
        String[] data = {"abcd","abcd","abcd","pwb2","abcd","pwb2","p12"};
        String[][] strings = topKString.topKstrings(data, 3);
        System.out.println(strings);
    }

    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        if(strings.length<k){
            return null;
        }
        Map<String,Integer> map = new HashMap<>();
        ArrayList<TopK> data = new ArrayList<>();
        for (String string : strings) {
            if(!map.containsKey(string)){
                map.putIfAbsent(string, 1);
            } else {
                map.computeIfPresent(string,(key,value) -> value+1);
            }
        }
        map.forEach((key,value) -> data.add(new TopK(key,value)));
        List<TopK> collect = data.stream().sorted()
                .limit(k)
                .collect(Collectors.toList());
        String[][] result = new String[collect.size()][2];
        for (int i = 0; i < collect.size(); i++) {
            result[i][0]=collect.get(i).string;
            result[i][1]=String.valueOf(collect.get(i).integer);
        }
        return result;
    }
}

class TopK implements Comparable<TopK>{

    public String string;
    public Integer integer;

    public TopK() {
    }

    public TopK(String string, Integer integer) {
        this.string = string;
        this.integer = integer;
    }

    @Override
    public int compareTo(TopK o) {

        if (o == null) {
            return -1;
        }
        if(this.integer>o.integer){
            return -1;
        } else if(this.integer<o.integer){
            return 1;
        } else {
           return compareString(this.string,o.string);
        }
    }

    public int compareString(String s1,String s2){
        byte[] bytes = s1.getBytes();
        byte[] bytes1 = s2.getBytes();
        int length = Math.min(s1.length(),s2.length());
        for (int i = 0; i < length; i++) {
            if(bytes[i]>bytes1[i]){
                return 1;
            } else {
                return -1;
            }
        }
        return 0;
    }
}
